#include<stdio.h>

// func1 O(n)
//int func1(int x, int n)
//{
//	int result = 1; // 注意 任何数的0次方等于1
//	
//	for(int i=1;i<=n;i++){
//		result = result * x;
//	}	
//	
//	return result;
//}

// func2 O(n)
//int func2(int x, int n)
//{
//	if (0 == n) return 1;

//	return func2(x, n-1) * x;
//}

// fun3 O(n)
//int func3(int x, int n)
//{
//	if (0 == n) return 1;
//	if (1 == n) return x;
//	
//	if (n%2 == 1)
//	{
//		return func3(x, n/2) * func3(x, n/2) * x;
//	}
//	else
//	{
//		return func3(x, n/2) * func3(x, n/2);
//	}
//}

// fun4 O(logn)
int func4(int x, int n)
{
	if (0 == n) return 1;
	if (1 == n) return x;
	
	int t = func4(x, n/2);
	if (n%2 == 1)
	{
		return t * t * x; // 这里相对于function3，是把这个递归操作抽取出来
	}
	else
	{
		return t * t;
	}
}

int main()
{
	int num = 0;
	printf("请输入2的n次方:");
	scanf("%d",&num);
	int ret = func4(2,num);
	
	printf("%d",ret);
	return 0;
}
